76. 最小覆盖子串

题目链接
注意，这个题是困难，以后困难题少花时间

分析

首先想到的，还是快慢指针这个框架，移动快慢指针的方式也很简单，

不满足条件就移动快指针
满足就移动慢指针，同时记录下最小长度，并记录下此时的慢指针，这样就能输出最后的字符串
那核心问题就是，如何判断一个子数组组包含一个字符串的所有字符。
首先想到的方法是，先统计目标字符串的所有字符串及其出现次数（我们甚至可以直接用 HashMap 来保存），然后再进行双指针移动的时候，记录并更新双指针确定的子数组中所有字符的出现次数，每移动一次就有目标字符串中的字符以及其个数对比一次，但是这样，每次对比都得循环目标字符串的所有字符。
有没有更高效的办法呢？有！
我们除了记录子字符串中的所有字符的个数之外，还额外使用一个变量，这个变量的作用是记录目标字符串中的字符，在当前子数组中的出现个数，规则如下
只有字符在当前子数组中出现的次数小于等于在目标字符串中出现的次数的时候，才累加这个变量
当我们移动慢指针的时候，如果移除字符之后，这个字符在当前子数组中出现的次数小于在目标字符串中出现的次数的时候，才减少这个变量。
这样，每次移动指针的时候，只要观察这个变量，我们就能知道当前子数组是否完全包含一个字符串的所有字符。
还有一个小技巧： ASCII 字符都有一个对应的 ASCII 码，所有 ASCII 字符有 128 个，我们可以将每一个字符的 ASCII 码当作下标，然后用下表对应的个数当作字符出现的个数，这样就可以不使用 HashMap 了。

参考哈希表就会明白：将一个字符的 ASCII 码当作下标，实际上就是一种哈希函数，key 就是字符，value 就是字符出现的次数

这个其实给了我们启发，所有对字符串包含的考察，我们都可以使用这个方法。

解题

这个题其实我一上来就有思路了，但是写的过程非常的难受，老是报错
有几点需要注意：
之前我都是习惯使用，[slow,fast) 例如 209. 长度最小的子数组，但是这个题不是，这个题用的是左闭右开区间 [slow,fast)，因此会出现一个极端情况，就是当遍历完数组的时候，fast==source.length，此时快指针实际上是超长了的，但是此时如果还可以收缩满指针，那么就不能直接退出，因此我们在 for 循环中不能使用 fast<source.length，这也是为什么官方题解都使用两层循环的原因，用两层循环的好处就是移动慢指针的时候不用考虑快指针的情况。

public String minWindow(String s, String t) {
    char[] targetCharArr = t.toCharArray();
    char[] sourceCharArr = s.toCharArray();
    int[] targetCount = new int[128];
    int[] sourceCount = new int[128];
    // 记录目标字符串中的字符出现次数
    for(int i=0;i<targetCharArr.length;i++){
        int charObj = targetCharArr[i];
        targetCount[charObj]++;
    }
    int count=0;
    // 子数组的不包含 fast，区间为[slow,fast)
    int slow=0,fast=0;
    int minLength = sourceCharArr.length+1;
    int startPoint = 0;
    for(;;){
        // 根据count判断移动快指针还是慢指针
        if(count<targetCharArr.length){
	        // 需要判断指针是否超出范围
            if(fast==sourceCharArr.length ){
                break;
            }
            int charFast = sourceCharArr[fast];
            // 不在目标字符串中出现的字符不统计
            if(targetCount[charFast]>0){
                sourceCount[charFast]+=1;
                // 如果子数组中，某个字符串的数量已经大于这个字符串在目标字符串中的数量，那count就没有再累加的必要了
                if(sourceCount[charFast]<=targetCount[charFast]){
                    count++;
                }    
            }
            fast++;
        }else{
            // 计算长度
            int nowLength = fast-slow;
            if(nowLength < minLength){
	            // 记录长度的同时记录起点，方便最后返回字符串
                minLength=nowLength;
                startPoint = slow;
            }
            // 需要判断指针是否超出范围
            if(slow==sourceCharArr.length ){
                break;
            }
            int charSlow = sourceCharArr[slow];
            // 不在目标字符串中出现的字符不统计
            if(targetCount[charSlow]>0){
                sourceCount[charSlow]-=1;
                // 字符在子数组中的数量小于在目标字符串中的数量，才减少count
                if(sourceCount[charSlow]<targetCount[charSlow]){
                    count--;
                }
            }
            slow++;
        }
    }
    if(minLength == sourceCharArr.length+1){
        return "";
    }
    return s.substring(startPoint,startPoint+minLength);

}

附赠官方题解

/**  
 * 优化思路：  
 * count 表示 字符在s中出现的频次  
 * count这个概念的引入成功实现了O(1)的时间按复杂度判断窗口内的元素是否包含t中所有的元素，对于需要保证元素出现次数的题目，都可以用count这个概念  
 * 此外，其实在 s 中，有的字符我们是不关心的，我们只关心 t 中出现的字符，在遍历过程中，我们完全可以跳过没在 t 中出现过的字符，避免没必要的对比  
 * 用来了ASCII码跟数字的对应关系，直接用一个长度为128(因为ASC代码总共128位) 的 int数组存放字符出现次数，省去了使用HashMap的内存和复杂度,  
 */public static String minWindow1(String s, String t) {  
    if (s.equals("") || s.length() == 0 || t .equals("") || t.length() == 0 || s.length() < t.length()) {  
        return "";  
    }  
    //题目中说 s 和 t 由英文字母组成 ，也就是说都是ASC代码，可以直接使用数字表示，那就直接当成数组下标，省去了使用HashMap的内存和复杂度  
    //数组存放指定字符出现的次数 数组长度为128，因为ASC代码总共128位  
    int[] need = new int[128];  
    int[] have = new int[128];  
    for (int i = 0; i < t.length(); i++) {  
        // int 类型默认值是0，不需要初始化  
        need[t.charAt(i)]++;  
    }  
    //t中的字符在s中出现的频次，这是一个很重要的概念，通过这个概念，可以直接判断滑动窗口中是否已经包含了t中所有的字符，真的是太棒了！！  
    int count = 0;  
    int scopeLeft = 0;  
    String result = "";  
    for (int scopeRight = 0; scopeRight < s.length(); scopeRight++) {  
        char charRight = s.charAt(scopeRight);  
        //无关的数据直接跳过  
        //每次操作have之前，都在need中对比一遍，可以节省大量的对比操作  
        if (need[charRight] == 0) {  
            continue;  
        }  
        have[charRight]++;  
        //这一步很精髓，count的值，实际上就是已经匹配的t中的元素的个数，  
        // charRight这个元素出现了t中出现的次数（need[charRight]），count就不再增加，这个不再增加的操作太妙了  
        if (have[charRight] <= need[charRight]) {  
            // have[charRight] 的数量可能超出 need[charRight]，只是超出之后，count 不会再增加  
            count++;  
        }  
        while (count == t.length()) {  
            if (result.equals("") || scopeRight - scopeLeft + 1 < result.length()) {  
                result = s.substring(scopeLeft, scopeRight + 1);  
            }  
            char charLeft = s.charAt(scopeLeft);  
            //无关的字符，直接跳过，不需要做任何比较  
            //每次操作have之前，都在need中对比一遍，可以节省大量的对比操作  
            if (need[charLeft] == 0) {  
                scopeLeft++;  
                continue;  
            }  
            //移除 s.charAt(scopeLeft) 就会破坏条件，所以count要变  
            if (have[charLeft] == need[charLeft]) {  
                // have[charLeft] 的数量是可能超出 need[charLeft]的，只有再减少到 need[charLeft] 之后，在减少才会影响条件  
                count--;  
            }  
            have[charLeft]--;  
            scopeLeft++;  
        }  
    }  
    return result;  
}

76. 最小覆盖子串

分析

解题

相关题